ABC344 D - String Bags
ざっくり問題
空文字列$ Sがある。
文字列のリストら$ L_1, L_2, \cdots, L_nが与えられたとする
それぞれのリストから"最大一つ"ずつ文字列を取って$ Sに末尾からそれらの要素を順々に結合したとき$ Tになる方法に対して、文字列を取る数$ nを考える。
$ nの最小値は？
解法
ナイーブな方法
一つ一つ組み合わせを探っていく。
時間がかかりすぎる。
全ての組み合わせをうまくまとめて探索できないだろうか？
観察
code:in
abcde
3
3 ab abc abcd
4 f c cd bcde
2 e de
abcdeに到達する方法はいくつか存在する。
ab -> abc -> abcde
abc -> abc -> abcde
"abc"から"abcde"を形成するまでの経路の選び方は、""から"abc"に到達するまでの経路に無関係。
abcまでどれだけのお金がかかったのかだけが大事なのであって、abcまでどう辿ったかは大事ではない
言い換えると...
abc -> abcdeでどういう選択をするかを考えるとき、abcまでの経路は（金額の情報を除いて）考えなくても良い。
組み合わせをまとめて探索するときに使えそう
abcの地点で最適な一手を選んでいなければ、どうやっても最適にはならない。
「かかったお金」が減ることはない。
abcまでの経路は、「最適な一手」だけに代表させることができる。
dpをこんなふうに定める。
dp_ij = { $ j文字目まで$ Sを構成し、$ i番目の袋への操作を終了した地点で、その状態に至るまでの最小の金額}
dp_ij == -1のとき、そのような状態に到達できないことを意味する。
std::vector<std::vector<int32_t>> dp(N, std::vector(T_len + 1, -1));
初期状態は全て到達不可(-1)にして、dp_00は0としておく。
（0文字目まで$ Sを構成し、$ 0番目の袋への操作を終了した地点でかかってる金額は$ 0）
更新方法
t_idx文字目まで構築している時を考える。
i個目の袋に操作を行っているときj文字目まで構築できているような状態に至る経路をループで全て探索する。
これは、i個目の袋に入っているそれぞれの文字列$ S_{i\_}に対して、
$ Sに追加する前の文字列長を求めて
const int32_t len_before_addition = t_idx - int32_t(S[i][_].size());
それがi-1個目の袋でlen_before_addition文字目まで構築できている状態にかかる金額を求めてやればいい。
min_money = std::min(min_money, dp[i-1][len_before_addition] + 1);
ここまでで、文字列を新しく追加する場合における最小の金額min_moneyを考えてきた。
それを、文字列を
実装に気をつけた点
実装が特にややこしくなる
変数一文字のものはできるだけ避けた。
また、タイプミスがあったときにパターンマッチングしやすくなる。
二次元配列Xがあったとして、S[i][str_idx]という記述があったときに、str_idxという添字が二番目に来ているから正しいだろう、と安心できる。
途中で一回テストを挟んだ。
でもWAx1が取れない！なんで？
結局、眺め続けて次のバグがわかった
min_money = std::min(min_money, dp[i-1][len_before_addition] + 1);が
min_money = std::min(min_money, dp[i][len_before_addition] + 1);になっていた
このようなミスをとっとと撃墜したい...。